﻿// 力扣：面试题 17.16. 按摩师
// 链接：https://leetcode.cn/problems/the-masseuse-lcci/description/
//（力扣：198.打家劫舍（LCR 089. 打家劫舍）与本题解题思路/代码一致！）

// 方法：动态规划
class Solution
{
public:
    int massage(vector<int>& nums)
    {
        int n = nums.size();            // 获取按摩次数的数量

        if (n == 0)
        {
            return 0;                   // 如果没有按摩次数，直接返回0
        }

        // 创建两个数组 f 和 g，用于记录每个位置的状态
        // f[i] 表示到第i次按摩时，按摩师能获得的最大金额（选择第i次按摩）
        // g[i] 表示到第i次按摩时，按摩师能获得的最大金额（不选择第i次按摩）
        vector<int> f(n);
        auto g = f;                     // g 和 f 数组一样，表示选择或不选择的状态

        // 如果选择第0次按摩，获得的金额就是 nums[0]，如果不选择第0次按摩，金额为0（写完发现g[0] = 0其实已经初始化了，没必要再初始化一次）
        f[0] = nums[0], g[0] = 0;       
                

        // 注意：从第二个按摩开始进行状态转移（即从第1次按摩开始）
        for (int i = 1; i < n; i++)
        {
            f[i] = g[i - 1] + nums[i];  // f[i]：选择第i次按摩时，最大金额为不选择上一次按摩的最大金额 + 当前按摩的金额 nums[i]
            g[i] = max(f[i - 1], g[i - 1]); // g[i]：不选择第i次按摩时，最大金额为选择上一次按摩的最大金额和不选择上一次按摩的最大金额中的较大值
        }

        return max(f[n - 1], g[n - 1]); // 最后返回最大值，表示最大可能获得的金额
    }
};